package Leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 解决找出数组中出现次数最多的k个元素的问题
 */
public class topKFrequent {
    /**
     * 定义一个内部类Pair来存储元素值和其出现频率
     */
    public class Pair{
        int value; // 元素值
        int feq;   // 元素出现频率

        public Pair(int value, int feq) {
            this.value = value;
            this.feq = feq;
        }
    }

    /**
     * 找出数组中出现次数最多的k个元素
     *
     * @param nums 输入的整数数组
     * @param k    需要找出的元素个数
     * @return     返回出现次数最多的k个元素组成的数组
     */
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        // 统计每个元素出现的频率
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }

        Pair[] pairs = new Pair[map.size()];
        int i = 0;
        // 将map中的元素转存到pairs数组中
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            pairs[i] = new Pair(entry.getKey(), entry.getValue());
            i++;
        }

        // 构建最大堆
        buildMaxHeap(pairs, pairs.length);
        int heapSize = pairs.length;
        List<Integer> res = new ArrayList<>();
        // 从堆中取出频率最高的k个元素
        for (int j = pairs.length - 1; j >= pairs.length - k; j--) {
            res.add(pairs[0].value);
            swap(pairs, 0, j);
            --heapSize;
            maxHeapify(pairs, 0, heapSize);
        }
        // 将结果转换为int数组返回
        return res.stream().mapToInt(Integer::intValue).toArray();
    }

    /**
     * 构建最大堆
     *
     * @param a        需要构建堆的数组
     * @param heapSize 数组的大小
     */
    public void buildMaxHeap(Pair[] a, int heapSize){
        for (int i = heapSize / 2 - 1; i >= 0; i--) {
            maxHeapify(a, i, heapSize);
        }
    }

    /**
     * 交换数组中的两个元素
     *
     * @param arr 需要进行元素交换的数组
     * @param i   第一个元素的索引
     * @param j   第二个元素的索引
     */
    public void swap(Pair[] arr, int i, int j) {
        Pair temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 堆调整
     *
     * @param a        需要调整的数组
     * @param i        需要调整的部分的根节点索引
     * @param heapSize 数组的大小
     */
    private void maxHeapify(Pair[] a, int i, int heapSize) {
        int left = i * 2 + 1, right = i * 2 + 2, largest = i;
        // 找出左右孩子中频率最大的
        if (left < heapSize && a[left].feq > a[largest].feq){
            largest = left;
        }
        if (right < heapSize && a[right].feq > a[largest].feq){
            largest = right;
        }
        // 如果根节点不是最大的，交换并继续调整
        if (largest != i){
            swap(a, i, largest);
            maxHeapify(a, largest, heapSize);
        }
    }
}
